package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author shkstart
 * @create 2021-08-21 1:16
 */
//归并排序法，不到一秒时间
public class MergetSort {
    public static void main(String[] args) {
        int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 }; //
        int [] s1={4,7,33,90};
        int[] ints = new int[s1.length];
        int[] temp = new int[arr.length];
        mergetSort(s1,0,s1.length-1,ints);
        System.out.println(Arrays.toString(s1));
//        int[] arr = new int[80000];
//        for (int i=0;i<80000;i++){
//            arr[i]=(int)(Math.random()*800000);
//        }
//        Date date1 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String format = simpleDateFormat.format(date1);
//        System.out.println("排序前的时间="+format);
//        int[] temp = new int[arr.length];
//        mergetSort(arr,0,arr.length-1,temp);
////        System.out.println(Arrays.toString(arr));
//        Date date2 = new Date();
////        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String format2 = simpleDateFormat.format(date2);
//        System.out.println("排序后的时间="+format2);

    }
//    //先分治再合并
//    public static void mergetSort(int[] arr,int left,int right,int[] temp){
//        if (left<right){
//            int mid=(left+right)/2;
//            //左边递归分解
//            mergetSort(arr,left,mid,temp);
//            //右边递归分解
//            mergetSort(arr,mid+1,right,temp);
//            //合并
//            Merget(arr,left,mid,right,temp);
//        }
//    }
    //先写合并的方法

    /**
     *
     * @param arr 传入的数组
     * @param left 左边那部分的开始索引
     * @param mid  左边那部分的结束索引
     * @param right  右边那边的开始索引
     * @param temp  替代的数组
     */
//    public static void Merget(int[] arr,int left,int mid,int right,int[] temp){
//        int i=left;//初始化左边开始的索引
//        int j=mid+1;//初始化右边开始的索引
//        int t=0;//数组temp的索引
//         //如果左边小于右边，那就可能还没循环结束
//        //(一)
//        //先把左右两边(有序)的数据按照规则填充到temp数组
//        //直到左右两边的有序序列，有一边处理完毕为止
//        while (i<=mid&&j<=right){
//            //如果左边小于右边的数字，那就提取左边的数字填入数组中
//          if (arr[i]<=arr[j]){
//              temp[t]=arr[i];
//              t++;
//              i++;
//          }else {
//              temp[t]=arr[j];
//              t++;
//              j++;
//          }
//
//        }
//        //(二)
//        //把有剩余数据的一边的数据依次全部填充到temp
//        //如果是左边还没完全输入，那就将剩余的部分输入
//        while (i<=mid){
//            temp[t]=arr[i];
//            t++;
//            i++;
//
//        }
//        //如果是右边还没完全输入，那就将剩余的部分输入
//        while (j<=right){
//            temp[t]=arr[j];
//            t++;
//            j++;
//        }
//        //(三)
//        //将temp数组的元素拷贝到arr
//        //注意，并不是每次都拷贝所有
//        //一次一次的合并,
//        t=0;
//        int templeft=left;
//        while (templeft<=right){
//            arr[templeft]=temp[t];
//            t++;
//            templeft++;
//        }
//
//
//    }
    public static void Merget(int[] arr,int left,int mid,int right,int[] temp){
        int i=left;
        int j=mid+1;
        int t=0;
        while (i<=mid&&j<=right){
            if (arr[i]<=arr[j]){
                temp[t++]=arr[i++];
            }else {
                temp[t++]=arr[j++];
            }
        }
        while (i<=mid){
            temp[t++]=arr[i++];
        }
        while (j<=right){
            temp[t++]=arr[j++];
        }
                t=0;
        int templeft=left;
        while (templeft<=right){
            arr[templeft++]=temp[t++];
        }
    }
    public static void mergetSort(int[] arr,int left,int right,int[] temp){
        if (left<right){
            int mid=(left+right)/2;
            mergetSort(arr,left,mid,temp);
            mergetSort(arr,mid+1,right,temp);
            Merget(arr,left,mid,right,temp);
        }
    }

}
